home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / delaunay_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.5 KB  |  226 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  delaunay_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_DELAUNAY_H
  17. #define LEDA_DELAUNAY_H
  18.  
  19. /*****************************************************************************
  20. +
  21. +    Delaunay tree    by Olivier Devillers
  22. +
  23. +        Fully dynamic construction of the Delaunay triangulation with
  24. +        good randomized complexity
  25. +
  26. +    Copyright (c) 1990
  27. +    INRIA, 2004 route des Lucioles, 06 565 Valbonne Cedex, France
  28. +
  29. +    for LEDA
  30. +    Copyright (c) 1990  by  Max Planck Institut f"ur Informatik
  31. +    Im Stadtwald, 6600 Saarbruecken, FRG
  32. +     All rights reserved.
  33. +
  34. ******************************************************************************/
  35.  
  36. #include <LEDA/point.h>
  37.  
  38. typedef double coord;
  39.  
  40. struct NOEUD;
  41. typedef NOEUD* noeud;
  42.  
  43. struct STAR;
  44. typedef STAR* star;
  45.  
  46. struct REINSERER;
  47. typedef REINSERER* reinserer;
  48.  
  49. struct LISTENOEUD;
  50. typedef LISTENOEUD* listenoeud;
  51.  
  52.  
  53. struct DT_POINT{
  54.     coord x,y;
  55.         void* i;
  56.     int  n;                   /* un flag dont l'ordre est compatible avec
  57.                           l'ordre d'insertion */
  58.     int  visite;           /* un flag de visite */
  59.     NOEUD* cree;    /*un noeud cree par l'insertion de ce point*/
  60. }; 
  61.  
  62. typedef DT_POINT* DT_item;
  63.  
  64.  
  65.  
  66. typedef void delaunay_f2(double,double);
  67. typedef void delaunay_f4(double,double,double,double);
  68. typedef void delaunay_f6(double,double,double,double,double,double);
  69. typedef void delaunay_F6(double,double,double,double,double*,double*);
  70.  
  71.  
  72.  
  73. class delaunay_tree{
  74.  
  75.         int flag;        /* numero de l'operation en cours */
  76.         noeud nouveau;        /* dernier noeud cree */
  77.         
  78.         star Star;        /* pour la suppression */
  79.         reinserer Reinsert;
  80.  
  81.     NOEUD * arbre ;        /* la racinne du Delaunay tree */
  82.     NOEUD * last ;        /* dernier noeud cree */
  83.  
  84.         int counter;            /* total number of items (s.n.) */
  85.  
  86.  
  87.  
  88. char*      used_blocks;
  89. DT_item    Poubelle_point;
  90. listenoeud Poubelle_listenoeud;
  91. noeud      Poubelle_noeud;
  92. noeud      Libre_noeud;
  93. star       Poubelle_star;
  94. reinserer  Poubelle_reinserer;
  95.  
  96. int fl;
  97.  
  98. int item_nombre;
  99. DT_item item_next;
  100.  
  101. int listenoeud_nombre;
  102. listenoeud listenoeud_next;
  103.  
  104. int noeud_nombre;
  105. noeud noeud_next;
  106.  
  107. int star_nombre;
  108. star star_next;
  109.  
  110. int reinserer_nombre;
  111. reinserer reinserer_next;
  112.  
  113. star first_star;
  114.  
  115.  
  116.  
  117. char*      alloc_block(int size);
  118. void       free_blocks();
  119. void       poubelle_point(DT_item p);
  120. DT_item    vrai_alloc_point();
  121. DT_item    alloc_point();
  122. void       poubelle_listenoeud(listenoeud p);
  123. listenoeud vrai_alloc_listenoeud();
  124. listenoeud alloc_listenoeud();
  125. void       poubelle_noeud(noeud p);
  126. noeud      vrai_alloc_noeud();
  127. noeud      alloc_noeud();
  128. void       poubelle_star(star p);
  129. star       vrai_alloc_star();
  130. star       alloc_star();
  131. void       poubelle_reinserer( reinserer p);
  132. reinserer  vrai_alloc_reinserer();
  133. reinserer  alloc_reinserer();
  134.  
  135. void  beaufils( noeud bf, noeud bp);
  136. void  plusbeaufils( noeud bf, noeud bp);
  137. void  demiplan( noeud t);
  138. void  cercle( noeud t);
  139. int   confondu( DT_item a, DT_item b);
  140. int   direct( noeud n);
  141. int   conflit( noeud n, DT_item p);
  142. noeud Insert( noeud n, DT_item p);
  143. noeud creenoeud( noeud pere, int i, DT_item p);
  144. int   creation( noeud detruit, DT_item p);
  145. DT_item localise( noeud detecte, DT_item p);
  146. void  add_x1x2( reinserer r, noeud v, DT_item p);
  147. void  add_decroche( reinserer r, noeud v);
  148. void  destroy( noeud u, DT_item p);
  149. void  recherche( DT_item p);
  150. void  reinsertion( reinserer n, DT_item p);
  151. void  parcours( reinserer n, DT_item p);
  152. void  trace_items(noeud, delaunay_f2*);
  153. void  list_items(noeud n, list<DT_item>& L);
  154. void  clear_items(noeud n);
  155. void  del_noeud( noeud n, delaunay_f4* trace_segment,int both);
  156. void  vor( noeud n, delaunay_f6* trace_segment, delaunay_F6* pt_infi, int both);
  157.  
  158. virtual void copy_inf(GenPtr& p)  { p=p; }
  159. virtual void clear_inf(GenPtr& p) { p=0; }
  160.  
  161. public:
  162.  
  163. delaunay_tree();
  164. virtual ~delaunay_tree();
  165.  
  166. reinserer locate( reinserer n, DT_item x);
  167. void clear_Reinsert( reinserer n);
  168. void clear_Star();
  169. void init_Star( noeud n, int i, int j, int k);
  170. star loc_Star( DT_item xx);
  171. void split_Star( star n1,star n2);
  172.  
  173. DT_item insert(double, double, void*);
  174.  
  175. DT_item insert(point p, void* inf) { return insert(p.xcoord(),p.ycoord(),inf); }
  176.  
  177. DT_item neighbor(double, double);
  178. DT_item neighbor(point p)          { return neighbor(p.xcoord(),p.ycoord()); }
  179. void    del(double, double);
  180. void    del(point p)               { del(p.xcoord(),p.ycoord()); }
  181. void    del_item( DT_item);
  182.  
  183. point    key(DT_item p)  { return point(p->x,p->y); } 
  184. void*    inf(DT_item p)  { return p->i; } 
  185.  
  186. void     change_inf(DT_item p, void* i)  { copy_inf(i);  
  187.                                            clear_inf(p->i); 
  188.                                            p->i = i; } 
  189.  
  190. void     trace_voronoi_sites( delaunay_f2*);
  191. void     trace_voronoi_edges( delaunay_f6*, delaunay_F6*, int both = 0);
  192. void     trace_triang_edges( delaunay_f4* , int both = 0);
  193.  
  194. void     all_items(list<DT_item>&);
  195.  
  196. void     convex_hull(list<DT_item>&);
  197.  
  198. void     clear();
  199. void     init();
  200.  
  201. };
  202.  
  203.  
  204.  
  205.  
  206. template<class itype>
  207.  
  208. class _CLASSTYPE DELAUNAY_TREE : public delaunay_tree {
  209.  
  210. void copy_inf(GenPtr& p)  { Copy(*(itype*)&p); }
  211. void clear_inf(GenPtr& p) { Clear(*(itype*)&p); }
  212.  
  213. public:
  214.  
  215. DT_item insert(point site, itype i)
  216.                           { return delaunay_tree::insert(site,Convert(i)); }
  217.  
  218. itype  inf(DT_item p)    { return itype(delaunay_tree::inf(p)); } 
  219.  
  220.  DELAUNAY_TREE() {}
  221. ~DELAUNAY_TREE() {}
  222.  
  223. };
  224.  
  225. #endif
  226.